from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # 选择方向
        op = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        m = len(matrix)
        n = len(matrix[0])
        i, j = 0, 0
        dx = 0
        ans = []
        # 一共需要访问 m*n次
        for _ in range(m * n):
            ans.append(matrix[i][j])
            matrix[i][j] = None  # 进行标记，表示已经访问过
            x, y = i + op[dx][0], j + op[dx][1]
            # 如果(x,y)出界 或者 已经访问过
            if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] is None:
                dx = (dx + 1) % 4  # 转换方向
            i += op[dx][0]
            j += op[dx][1]
        return ans
